From Nand to Tetris week 1

这周开始学习From Nand to Tetris，中文名为“依据基本原理构建现代计算机：从与非门到俄罗斯方块”，课程介绍了计算机的工作原理，每周有一个项目，完成课程之后，可以真正构建出一个可以运行的计算机，课程也没有太多的先修课程，只要学过任何一门编程语言即可。

课程官网：

https://www.nand2tetris.org/

视频地址：

https://www.coursera.org/learn/build-a-computer

Chapter 1 布尔逻辑

Part 1：课程回顾

第一讲的内容比较基础，下面回顾几个重点部分：

Bool逻辑与Bool函数

课程首先介绍Bool逻辑的常用性质，这里假设我们只使用$\text{And,Not,Or}$操作。比较关键的一点是Bool表达式对应了真值表，例如

$$f(x, y, z) = (x\text{ And }y)\text{ Or }(\text{Not}(x)\text{ And }z)$$

对应了

$x$	$y$	$z$	$f$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

这部分表示Bool表达式$\Rightarrow$真值表，一个比较自然的问题是如何从真值表推出Bool表达式？

考虑如下例子：

$x$	$y$	$z$	$f$
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	0

构造方法很简单，首先考虑只在$f$取$1$的点处取$1$的表达式，例如此处为

$$\begin{aligned} &\text{Not}(x)\text{ And Not}(y)\text{ And Not}(z) \\ &\text{Not}(x)\text{ And }y\text{ And Not}(z)\\ &x\text{ And Not}(y)\text{ And Not}(z) \end{aligned}$$

然后将上述三个表达式取$\text{Or}$即得到目标表达式：

$$\begin{aligned} &(\text{Not}(x)\text{ And Not}(y)\text{ And Not}(z))\text{ Or} \\ &(\text{Not}(x)\text{ And }y\text{ And Not}(z))\text{ Or}\\ &(x\text{ And Not}(y)\text{ And Not}(z)) \end{aligned}$$

不难将上述方法推广到任意Bool表达式的构造，注意每个Bool函数可以用真值表表示，所以我们得到如下引理：

引理1

$$任何\text{Bool}函数都可以只使用\text{And,Not,Or}表达$$

因为

$$(x\text{ Or }y) = \text{Not}(\text{Not}(x)\text{ And Not}(y))$$

所以实际上我们有更强的结论：

引理2

$$任何\text{Bool}函数都可以只使用\text{And,Not}表达$$

我们能否做的更好呢？不难看出在使用$\text{And,Not,Or}$的要求下，我们已经达到最优情形，因为$\text{Not}$无法表达$\text{And}$，反过来也是如此。但是如果可以使用别的逻辑操作，那么可以减少基础逻辑操作符的数量，考虑如下逻辑操作符$\text{Nand}$。

Nand门输入输出关系如下

$x$	$y$	$\text{Nand}(x,y)$
$0$	$0$	$1$
$0$	$1$	$1$
$1$	$0$	$1$
$1$	$1$	$0$

即

$$\text{Nand}(a,b)=\text{Not}(x\text{ And }y)$$

不难验证

$$\begin{aligned} &\text{Not}(x) =\text{Nand}(x,x)\\ &\text{And}(x, y) =\text{Not}(\text{Nand}(x,y)) \end{aligned}$$

所以有如下定理：

定理

$$任何\text{Bool}函数都可以只使用\text{Nand}表达$$

本课程中使用的基础逻辑操作为$\text{Nand}$。

HDL(Hardware description language)

本课程使用HDL编程语言来设计逻辑电路，具体的形式如下：

/** Xor gate: out = (a And Not(b)) Or (Not(a) And b)) */
CHIP Xor {
    IN a, b;
    OUT out;
    PARTS:
    // Implementation missing
}

具体的使用方法可以参考课本附录以及官网，注意HDL无法编译运行，但是可以使用老师提供的模拟器查看输入输出，这部分在视频中有详细介绍。

Part 2：项目

第一次项目使用Nand门构造常用的逻辑单元，推荐开发环境为VSCODE+Nand2Tetris插件。

芯片接口：

Nand

Nand门输入输出关系如下

$a$	$b$	$\text{Nand}(a,b)$
$0$	$0$	$1$
$0$	$1$	$1$
$1$	$0$	$1$
$1$	$1$	$0$

Not

考虑$\text{Nand}(a,a)$

$a$	$a$	$\text{Nand}(a,a)$
$0$	$0$	$1$
$0$	$0$	$1$
$1$	$1$	$0$
$1$	$1$	$0$

说明

$$\text{Not}(a) =\text{Nand}(a,a)$$

And

$\text{Nand}(a,b)$的特点，不难发现有

$$\text{And}(a, b) =\text{Not}(\text{Nand}(a,b))$$

Or

$$\text{Or}(a, b) = \text{Not}(\text{And}(\text{Not}(a),\text{Not}(b)))$$

XOR

XOR门输入输出关系如下

$a$	$b$	$\text{XOR}(a,b)$
$0$	$0$	$0$
$0$	$1$	$1$
$1$	$0$	$1$
$1$	$1$	$0$

所以有如下逻辑关系

$$\text{Or}(\text{And}(a, \text{Not}(b)), \text{And}(b, \text{Not}(a)))$$

Mux

Mux是选择器，输入为$a,b,\text{sel}$

$\text{sel}$	$\text{out}$
$0$	$a$
$1$	$b$

第一行相当于

$$\text{And}(\text{Not}(\text{sel}), a)$$

第二行相当于

$$\text{And}(\text{sel}, b)$$

合并起来即为

$$\text{Mux}(a,b,\text{sel})= \text{Or}(\text{And}(\text{Not}(\text{sel}), a),\text{And}(\text{sel}, b))$$

DMux

DMux的作用如下：

• if (sel==0)
  • {a,b}={in,0}
• else
  • {a,b}={0,in}

真值表为

$\text{in}$	$\text{sel}$	$\text{Not}(\text{sel})$	$a$	$b$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$0$	$0$	$0$
$1$	$0$	$1$	$1$	$0$
$1$	$1$	$0$	$0$	$1$

从真值表中，不难看出我们有

$$\begin{aligned} a&=\text{Mux}(\text{in},\text{false},\text{sel})\\ b&=\text{Mux}(\text{in},\text{false},\text{Not}(\text{sel})) \end{aligned}$$

2020/9/20二刷更新：

逻辑关系其实很简单：

$$\begin{aligned} a&=\overline{\text{sel}} .\text{in}\\ b&=\text{sel}.\text{in} \end{aligned}$$

Not16

这个比较简单，只要对每一位取$\text{Not}$即可，注意这里没有循环。

And16

对$a[16]$与$b[16]$每一位取$\text{And}$即可。

OR16

利用

$$\text{Or16}(a, b) = \text{Not16}(\text{And16}(\text{Not16}(a),\text{Not16}(b)))$$

Mux16

根据$\text{sel}$对$a[16]$与$b[16]$每一位取$\text{Mux}$即可。

Or8Way

逐步计算下式即可

$$\text{(in[0] Or in[1] Or ... Or in[7])}$$

Mux4Way16

Mux4Way16的作用如下

• out = a if sel == 00
  • b if sel == 01
  • c if sel == 10
  • d if sel == 11

所以可以根据$\text{sel}[0]$在$a,b$之间以及$c,d$之间做选择，然后根据$\text{sel}[1]$在第一步的结果之间做选择。

（备注，$\text{sel}[0]$为最右边的数字）

Mux8Way16

Mux8Way16和Mux4Way16作用类似，是对$8$个输入做选择，先根据$\text{sel}[0..1]$对前四个以及后四个做选择，然后根据$\text{sel}[2]$在第一步的结果之间做选择。

DMux4Way

• 4-way demultiplexor:
• {a, b, c, d} =
  • {in, 0, 0, 0} if sel == 00
  • {0, in, 0, 0} if sel == 01
  • {0, 0, in, 0} if sel == 10
  • {0, 0, 0, in} if sel == 11

第一步只考虑$\text{sel}[0]$，使用DMux产生如下效果

{a1, b1, c1, d1} =

• {in, 0, in, 0} if sel == 00
• {0, in, 0, in} if sel == 01
• {in, 0, in, 0} if sel == 10
• {0, in, 0, in} if sel == 11

对应代码如下

DMux (in=in, sel=sel[0], a=a1, b=b1);
DMux (in=in, sel=sel[0], a=c1, b=d1);

第二步考虑$\text{sel}[1]$，使用Mux产生如下效果

{a, b, c, d} =

• {in, 0, 0, 0} if sel == 00
• {0, in, 0, 0} if sel == 01
• {0, 0, in, 0} if sel == 10
• {0, 0, 0, in} if sel == 11

对应代码如下：

Not (in=sel[1], out=notsel1);
Mux (a=a1, b=notsel1, sel=sel[1], out=a);
Mux (a=b1, b=notsel1, sel=sel[1], out=b);
Mux (a=sel[1], b=c1, sel=sel[1], out=c);
Mux (a=sel[1], b=d1, sel=sel[1], out=d);

注意如下代码也可以：

Mux(a=a1, b=false, sel=sel[1], out=a);
Mux(a=b1, b=false, sel=sel[1], out=b);
Mux(a=false, b=c1, sel=sel[1], out=c);
Mux(a=false, b=d1, sel=sel[1], out=d);

DMux8Way

和DMux4Way一样的思路，分两步操作，根据$\text{sel}[0..1]$对$a,b,c,d$以及$e,f,g,h$用DMux4Way分别处理，然后利用根据$\text{sel}[2]$使用Mux处理。

DMux4Way(in=in, sel=sel[0..1], a=a1, b=b1, c=c1, d=d1);
DMux4Way(in=in, sel=sel[0..1], a=e1, b=f1, c=g1, d=h1);
Mux(a=a1, b=false, sel=sel[2], out=a);
Mux(a=b1, b=false, sel=sel[2], out=b);
Mux(a=c1, b=false, sel=sel[2], out=c);
Mux(a=d1, b=false, sel=sel[2], out=d);
Mux(a=false, b=e1, sel=sel[2], out=e);
Mux(a=false, b=f1, sel=sel[2], out=f);
Mux(a=false, b=g1, sel=sel[2], out=g);
Mux(a=false, b=h1, sel=sel[2], out=h);